class Solution:
    def maxProfit(self, prices):
        self.prices = prices
        self.max_profit = 0
        self.suffixProfit(len(prices) - 1)
        return self.max_profit

    def suffixProfit(self, i):
        if i == 0: return  0
        pre = self.suffixProfit(i - 1)
        diff = self.prices[i] - self.prices[i - 1]
        cur = pre + diff if pre+diff >= 0 else 0
        print("i=%d pre= %d cur=%d diff= %d" % (i,pre,cur,diff))
        self.max_profit = max(cur, self.max_profit)
        return cur
